%===================================================================================
\section{Serial example problems}\label{s:ex_serial}
%===================================================================================

\subsection{A dense example: idaRoberts\_dns}\label{ss:idaRoberts}

This example, due to Robertson~\cite{Rob:66}, is a model of a three-species 
chemical kinetics system written in DAE form. Differential equations are given 
for species $y_1$ and $y_2$ while an algebraic equation determines $y_3$. The 
equations for the species concentrations $y_i(t)$ are:
\begin{equation}\label{e:idaRoberts_DAE}
\begin{cases}
  y^\prime_1 &= -.04 y_1 + 10^4 y_2 y_3   \\
  y^\prime_2 &= +.04 y_1 - 10^4 y_2 y_3 - 3 \cdot 10^7 y_2^2  \\
  0 &=  y_1 + y_2 + y_3 - 1 \, .
\end{cases}
\end{equation}
The initial values are taken as $y_1 = 1$, $y_2 = 0$, and $y_3 = 0$
This example computes the three concentration components on the interval
from $t=0$ through $t=4 \cdot 10^{10}$.
While integrating the system, the program also use the rootfinding
feature to find the points at which $y_1 = 10^{-4}$ or at which
$y_3 = 0.01$.

We give a rather detailed explanation of the parts of the program and
their interaction with {\ida}.

Following the initial comment block, this program has a number
of \id{\#include} lines, which allow access to useful items in {\ida}
header files.  The \id{sundials\_types.h} file provides the definition of the
type \id{sunrealtype} (see \ugref{s:types} in the user guide \cite{ida_ug}
for details).  For now, it suffices to read \id{sunrealtype} as \id{double}.
The \id{ida.h} file provides prototypes for the {\ida}
functions to be called (excluding the linear solver selection
function), and also a number of constants that are to be used in
setting input arguments and testing the return value of \id{IDASolve}.
The \id{nvector\_serial.h} file is the header file for the serial
implementation of the {\nvector} module and includes definitions of the 
\id{N\_Vector} type, a macro to access vector components, and prototypes 
for the serial implementation specific machine environment memory allocation
and freeing functions.
Finally, note that the include files \id{sunmatrix\_dense.h} and
\id{sunlinsol\_dense.h} include definition of the dense matrix and
linear solver modules, as well as a macro for accessing matrix elements.

This program includes the user-defined accessor macro
\id{IJth} that is useful in writing the problem functions in a form
closely matching the mathematical description of the DAE system,
i.e. with components numbered from 1 instead of from 0.
The \id{IJth} macro is used to access elements of a dense matrix of
type \id{sunmatdense}. It is defined using the accessor macro
\id{SM\_ELEMENT\_D} which numbers matrix rows and columns starting with
0. The macro \id{SM\_ELEMENT\_D} is fully described in \ugref{ss:sunmat_dense}.

The program prologue ends with prototypes of the three user-supplied functions 
that are called by {\ida} and the prototypes of five private functions.
Of the latter, the four \id{Print***} functions perform printing
operations, and  \id{check\_flag} tests the return flag from the {\ida}
user-callable functions.

After various declarations, the \id{main} program begins by
allocating memory for the \id{yy}, \id{yp}, and \id{avtol} vectors using
\id{N\_VNew\_Serial} with a length argument of \id{NEQ} ($= 3$). The
lines following that load the initial values of the dependent
variable vectors into \id{yy} and \id{yp}, and set the relative tolerance 
\id{rtol} and absolute tolerance vector \id{avtol}. Serial \id{N\_Vector} 
values are set by first accessing the pointer to their underlying data using
the macro \id{NV\_DATA\_S} defined by {\nvecs} in \id{nvector\_serial.h}.

The calls to \id{N\_VNew\_Serial}, and also later calls to \id{IDA***}
functions, make use of a private function, \id{check\_flag}, which examines
the return value and prints a message if there was a failure.  This
\id{check\_flag} function was written to be used for any serial {\sundials}
application.

The call to \id{IDACreate} creates the {\ida} solver memory block.
The return value of this function is a pointer to the memory block for this
problem.  In the case of failure, the return value is \id{NULL}.  This
pointer must be passed in the remaining calls to {\ida} functions.

The call to \id{IDAInit} allocates the solver memory block.
Its arguments include the name of the {\CC} function \id{resrob} defining the
residual function $F(t,y,y')$, and the initial values of $t$, $y$, and $y'$.
The call to \id{IDASVtolerances} specifies a vector of absolute tolerances, and
this call includes the relative tolerance \id{rtol} and the absolute tolerance
vector \id{avtol}.  See \ugref{sss:idainit} and \ugref{sss:idatolerances}
for full details of these calls.  (The \id{avtol} vector is then freed,
because {\ida} keeps a separate copy of it.)

The call to \id{IDARootInit} specifies that a rootfinding problem
is to be solved along with the integration of the DAE system, that the
root functions are specified in the function \id{grob}, and that there are
two such functions.  Specifically, they are set to $y_1 - 0.0001$ and 
$y_3 - 0.01$, respectively.
See \ugref{ss:idarootinit} for a detailed description of this call.

The calls to \id{SUNDenseMatrix} (see \ugref{ss:sunmat_dense}),
\id{SUNLinSol\_Dense} (see \ugref{ss:sunlinsol_dense}),
\id{IDASetLinearSolver} (see \ugref{sss:lin_solv_init})
and \id{IDASetJacFn} (see \ugref{sss:optin_ls}) specify the {\sunlinsoldense}
linear solver with an analytic Jacobian supplied by the user-supplied function
\id{jacrob}.

The actual solution of the DAE initial value problem is accomplished in
the loop over values of the output time \id{tout}.  In each pass of the
loop, the program calls \id{IDASolve} in the \id{IDA\_NORMAL} mode, meaning
that the integrator is to take steps until it overshoots \id{tout} and then
interpolate to $t =  $\id{tout}, putting the computed value of $y$(\id{tout})
and $y'$(\id{tout}) into \id{yy} and \id{yp}, respectively, with
\id{tret} = \id{tout}.  The return value in this case is \id{IDA\_SUCCESS}.
However, if \id{IDASolve} finds a root before reaching the next value
of \id{tout}, it returns \id{IDA\_ROOT\_RETURN} and stores the root
location in \id{tret} and the solution there in \id{yy} and \id{yp}.  In
either case, the program prints $t$ (= \id{tret}) and \id{yy}, and
also the cumulative number of steps taken so far, and the current
method order and step size.
In the case of a root, the program calls \id{IDAGetRootInfo} to get a
length-2 array \id{rootsfound} of bits showing which root function was
found to have a root.  If \id{IDASolve} returned any negative value
(indicating a failure), the program breaks out of the loop.  In the
case of a \id{IDA\_SUCCESS} return, the value of \id{tout} is advanced
(multiplied by 10) and a counter (\id{iout}) is advanced, so that the
loop can be ended when that counter reaches the preset number of
output times, \id{NOUT} = 12.  See \ugref{sss:idasolve} for full
details of the call to \id{IDASolve}.

Finally, the main program calls \id{PrintFinalStats} to extract and
print several relevant statistical quantities, such as the total
number of steps, the number of residual and Jacobian evaluations, and
the number of error test and convergence test failures.  It then calls
\id{IDAFree} to free the {\ida} memory block and \id{N\_VDestroy\_Serial}
to free the vectors \id{yy} and \id{yp}.

The function \id{PrintFinalStats} used here is actually suitable for
general use in applications of {\ida} to any problem with a dense
Jacobian.  It calls various \id{IDAGet***} 
functions to obtain the relevant counters, and then prints them.
Specifically, these are: the cumulative number of steps (\id{nst}), 
the number of residual evaluations (\id{nre}) (excluding those for
difference-quotient Jacobian evaluations),
the number of residual evaluations for Jacobian evaluations (\id{nreLS}),
the number of Jacobian evaluations (\id{nje}),
the number of nonlinear (Newton) iterations (\id{nni}),
the number of local error test failures (\id{netf}),
the number of nonlinear convergence failures (\id{ncfn}),
and the number of \id{grob} (root function) evaluations (\id{nge}).
These optional outputs are described in \ugref{ss:optional_output}.

The functions \id{resrob} (of type \id{IDAResFn}) and \id{jacrob} (of type
\id{IDALsJacFn}) are straightforward expressions of the DAE system
(\ref{e:idaRoberts_DAE}) and its system Jacobian.  The function \id{jacrob}
makes use of the macro \id{IJth} discussed above.  See \ugref{ss:resFn}
for detailed specifications of \id{IDAResFn}.  Similarly, the function
\id{grob} defines the two functions, $g_0$ and $g_1$, whose roots are
to be found.  See \ugref{ss:rootFn} for a detailed description of the
\id{grob} function.

The output generated by \id{idaRoberts\_dns} is shown below.  It shows the output
values at the 12 preset values of \id{tout}.  It also shows the two root
locations found, first at a root of $g_1$, and then at a root of $g_0$.
%%
\includeOutput{idaRoberts\_dns}{../../examples/ida/serial/idaRoberts_dns.out}
%%
%-----------------------------------------------------------------------------------

\subsection{A banded example: idaFoodWeb\_bnd}\label{ss:idaFoodWeb}

This example is a model of a multi-species food web \cite{Bro:86}, in
which predator-prey relationships with diffusion in a 2-D spatial
domain are simulated.  Here we consider a model with $s = 2p$ species:
$p$ predators and $p$ prey.  Species $1,\ldots, p$ (the prey) satisfy
rate equations, while species $p+1,\ldots, s$ (the predators) have
infinitely fast reaction rates.  The coupled PDEs for the species
concentrations $c^i(x,y,t)$ are:
\begin{equation}\label{e:idaFoodWeb_PDE}
  \begin{cases}
    \partial c^i / \partial t = R_i(x,y,c) + d_i 
    ( c^i_{xx} + c^i_{yy} ) \, ~~ i = 1,2,\ldots,p \\
    \hspace*{.36in}        0 = R_i(x,y,c) + d_i 
    ( c^i_{xx} + c^i_{yy} ) \, ~~ i = p+1,\ldots,s ~,
  \end{cases}
\end{equation}
with
\[
R_i(x,y,c) = c^i \left( b_i + \sum_{j=1}^s a_{ij} c^j \right) \, .
\]
Here $c$ denotes the vector $\{c^i\}$.
The interaction and diffusion coefficients $(a_{ij},b_i,d_i)$ can be
functions of $(x,y)$ in general. The choices made for this test
problem are as follows:
%%
\begin{equation*}
  a_{ij} = 
  \begin{cases}
    -1                 & i=j \\
    -0.5 \cdot 10^{-6} & i \leq p , ~ j > p  \\
    10^4               & i > p , ~ j \leq p  \\
    0                  & \mbox{all other } (i,j) \, ,
  \end{cases}
\end{equation*}
%%
\begin{equation*}
  b_i = b_i(x,y) = 
  \begin{cases}
    (1 + \alpha xy + \beta \sin(4\pi x)\sin(4\pi y) )  & i \leq p  \\
    - (1 + \alpha xy + \beta \sin(4\pi x)\sin(4\pi y) )  & i > p \, ,
  \end{cases}
\end{equation*}
and
%%
\begin{equation*}
  d_i = 
  \begin{cases}
    1 & i \leq p  \\
    0.5 & i > p  \, .
  \end{cases}
\end{equation*}

The spatial domain is the unit square $0 \leq x,y \leq 1$, and the
time interval is $0 \leq t \leq 1$.  The boundary conditions are of
homogeneous Neumann type (zero normal derivatives) everywhere.  
The coefficients
are such that a unique stable equilibrium is guaranteed to exist when
$\alpha = \beta = 0$ \cite{Bro:86}.  Empirically, a stable equilibrium
appears to exist for (\ref{e:idaFoodWeb_PDE}) when $\alpha$ and $\beta$ are
positive, although it may not be unique. In this problem we take
$\alpha = 50$ and $\beta = 1000$.  For the initial conditions, we set
each prey concentration to a simple polynomial profile satisfying the
boundary conditions, while the predator concentrations are all set to
a flat value:
\begin{equation*}
c^i(x,y,0) = 
\begin{cases}
  10 + i [16x(1 - x)y(1 - y)]^2 & i \leq p \, , \\
  10^5                          & i > p \, .
\end{cases}
\end{equation*}

We discretize this PDE system (\ref{e:idaFoodWeb_PDE}) (plus boundary conditions)
with central differencing on an $L \times L$ mesh, so as to obtain a
DAE system of size $N = s L^2$.  The dependent variable vector $C$
consists of the values $c^i(x_j,y_k,t)$ grouped first by species index
$i$, then by $x$, and lastly by $y$.  At each spatial mesh point, the
system has a block of $p$ ODE's followed by a block of $p$ algebraic
equations, all coupled.
For this example, we take $p = 1, s = 2$, and $L = 20$.
The Jacobian is banded, with half-bandwidths \id{mu = ml} $= sL = 40$.

The \id{idaFoodWeb\_bnd.c} program includes the files
\id{sunmatrix\_band.h} and \id{sunlinsol\_band.h} in order
to use the {\sunlinsolband} linear solver. 
The former of these files contains the definition for the band matrix
type {\sunmatband}, and the \id{SM\_COLUMN\_B} and
\id{SM\_COLUMN\_ELEMENT\_B} macros for accessing matrix elements. See
\ugref{ss:sunmat_band}. 
The main {\ida} header file \id{ida.h} is included for the prototypes of the
solver user-callable functions and {\ida} constants, while the file
\id{nvector\_serial.h} is included for the definition of the serial
\id{N\_Vector} type.  The header file \id{sundials\_dense.h} is included for the
\id{newDenseMat} function used in allocating memory for the user data structure.

The include lines at the top of the file are followed by definitions of
problem constants which include the $x$ and $y$ mesh dimensions, \id{MX} and
\id{MY}, the number of equations \id{NEQ}, the scalar relative and absolute
tolerances \id{RTOL} and \id{ATOL}, and various parameters for the food-web problem.

Spatial discretization of the PDE naturally produces a DAE system in
which equations are numbered by mesh coordinates $(i,j)$. The
user-defined macro \id{IJth\_Vptr} isolates the translation for the
mathematical two-dimensional index to the one-dimensional
\id{N\_Vector} index and allows the user to write clean, readable code
to access components of the dependent variable. \id{IJ\_Vptr(v,i,j)}
returns a pointer to the location in \id{v} corresponding to the species
with index \id{is} $= 0$, x-index \id{ix} $= i$, and y-index \id{jy} $= j$.

The type \id{UserData} is a pointer to a structure containing problem
data used in the \id{resweb} function.  This structure is
allocated and initialized at the beginning of \id{main}. The pointer
to it, called \id{webdata}, is then passed to \id{IDASetUserData} and as a result 
it will be passed back to the \id{resweb} function each time it is called.

The \id{main} program is straightforward and very similar to that for \id{idaRoberts\_dns}.
The differences come from the use of the {\sunlinsolband} linear solver and from the
use of the consistent initial conditions algorithm in {\ida} to correct the initial
values. The call to \id{SUNBandMatrix} includes the half-bandwidths \id{ml} and \id{mu}.
\id{IDACalcIC} is called with the option \id{IDA\_YA\_YDP\_INIT}, meaning
that {\ida} is to compute the algebraic components of $y$ and differential  
components of $y'$, given the differential components of $y$.  
This option requires that the \id{N\_Vector} \id{id} be set through a call to 
\id{IDASetId} specifying the differential and algebraic components. In this example,
\id{id} has components equal to $1$ for the prey (indicating differential 
variables) and $0$ for the predators (algebraic variables).

Next, the \id{IDASolve} function is called in a loop over the output times,
and the solution for the species concentrations at the bottom-left and
top-right corners is printed, along with the cumulative number of time
steps, current method order, and current step size.

Finally, the main program calls \id{PrintFinalStats} to get and print
all of the relevant statistical quantities.  It then calls \id{N\_VDestroy\_Serial}
to free the vectors \id{cc}, \id{cp}, and \id{id}, and \id{IDAFree} to free the 
{\ida} memory block.

The function \id{PrintFinalStats} used here is actually suitable for
general use in applications of {\ida} to any problem with a banded
Jacobian.  It calls various \id{IDAGet***} 
functions to obtain the relevant counters, and then prints them.
Specifically, these are: the cumulative number of steps (\id{nst}), 
the number of residual evaluations (\id{nre}) (excluding those for
difference-quotient Jacobian evaluations),
the number of residual evaluations for Jacobian evaluations (\id{nreLS}),
the number of Jacobian evaluations (\id{nje}),
the number of nonlinear (Newton) iterations (\id{nni}),
the number of local error test failures (\id{netf}),
and the number of nonlinear convergence failures (\id{ncfn}).
These optional outputs are described in \ugref{ss:optional_output}.

The function \id{resweb} is a direct translation of the residual of
(\ref{e:idaFoodWeb_PDE}).  It first calls the private function \id{Fweb} to
initialize the residual vector with the right-hand side of (\ref{e:idaFoodWeb_PDE})
and then it loops over all grid points, setting residual values appropriately for 
differential or algebraic components. The calculation of the interaction terms
$R_i$ is done in the function \id{WebRates}.


Sample output from \id{idaFoodWeb\_bnd} follows.
%%
\includeOutput{idaFoodWeb\_bnd}{../../examples/ida/serial/idaFoodWeb_bnd.out}
%%

%-----------------------------------------------------------------------------------

\subsection{A Krylov example: idaHeat2D\_kry}\label{ss:idaHeat2D}

This example solves a discretized 2D heat PDE problem. The DAE system
arises from the Dirichlet boundary condition $u = 0$, along with the 
differential equations arising from the discretization of the interior 
of the region. 

The domain is the unit square $\Omega = \{ 0 \le x,y \le 1 \}$ and the
equations solved are:
\begin{equation}\label{e:idaHeat2D_PDE}
\begin{cases}
  \partial u / \partial t = u_{xx} + u_{yy}  & (x,y) \in \Omega \\
  u = 0 & (x,y) \in \partial\Omega\, .
\end{cases}
\end{equation}
The time interval is $0 \leq t \leq 10.24$, and the initial conditions are 
$u = 16x(1-x)y(1-y)$.

We discretize the PDE system (\ref{e:idaHeat2D_PDE}) (plus boundary conditions)
with central differencing on a $10 \times 10$ mesh, so as to obtain a
DAE system of size $N = 100$.  The dependent variable vector $u$
consists of the values $u(x_j,y_k,t)$ grouped first by $x$, and then
by $y$.  Each discrete boundary condition becomes an algebraic equation
within the DAE system.

In this case, \id{sunlinsol\_spgmr.h} is included for the definitions of
constants and function prototypes associated with the
{\sunlinsolspgmr} linear solver module.

After various initializations (including a vector of constraints with
all components set to $1$, imposing all solution components to be
non-negative), the main program creates and initializes the {\ida}
memory block.  It then creates the {\sunlinsolspgmr} linear solver
using the default \id{MODIFIED\_GS} Gram-Scmidt orthogonalization
algorithm, and updates the number of allowed {\spgmr} restarts to 5.
It then attaches this linear solver module to {\ida} with a call to
\id{IDASetLinearSolver}.

The user-supplied preconditioner setup and solve functions, \id{PsetupHeat}
and \id{PsolveHeat}, and the pointer to user data (\id{data}) are specified
in a call to \id{IDASetPreconditioner}.
%%
In a loop over the desired output times, \id{IDASolve} is called in \id{IDA\_NORMAL}
mode and the maximum solution norm is printed.
Following this, three more counters are printed.

The \id{main} program then re-initializes the {\ida} solver and the
{\sunlinsolspgmr} linear solver and solves the problem again, this time
using the \id{CLASSICAL\_GS} Gramm-Schmidt orthogonalization algorithm.
%%
Finally, memory for the {\ida} solver and for the various vectors used is deallocated.

The user-supplied residual function \id{resHeat}, of type \id{IDAResFn},
loads the DAE residual with the value of $u$ on the boundary
(representing the algebraic equations expressing the boundary
conditions of (\ref{e:idaHeat2D_PDE})) and with the spatial discretization 
of the PDE (using central differences) in the rest of the domain.

The user-supplied functions \id{PsetupHeat} and \id{PsolveHeat} together define the 
left preconditioner matrix $P$ approximating the system Jacobian matrix
$J = \partial F/ \partial u + \alpha \partial F/ \partial u'$ (where the DAE
system is $F(t,u,u') = 0$), and solve the linear systems $P z = r$.   
Preconditioning  is done in this case by keeping only the diagonal elements of 
the $J$ matrix above, storing them as inverses in a vector \id{pp}, when computed
in \id{PsetupHeat}, for subsequent use in \id{PsolveHeat}.
%%
In this instance, only \id{cj} $=\alpha$ and \id{data} (the user data
structure) are used from the \id{PsetupHeat} argument list.

Sample output from \id{idaHeat2D\_kry} follows.
%%
\includeOutput{idaHeat2D\_kry}{../../examples/ida/serial/idaHeat2D_kry.out}
%%
%-----------------------------------------------------------------------------------
\subsection{A sparse direct example: idaHeat2D\_klu}\label{ss:idaHeat2Dklu}

We provide an example of using {\ida} with the KLU sparse direct solver module
{\sunlinsolklu} that solves the same 2D heat PDE problem as \id{idaHeat2D\_kry}
with the same zero Dirichlet boundary conditions and central differencing but
with no preconditioner. This example is mainly based off of the
\id{idaHeat2D\_bnd} example program.

Due to the nature of the Jacobian matrix of the 2D heat PDE problem in column
major format, in order to store the Jacobian in compressed sparse column (CSC)
format, it was necessary to have two separate user-supplied Jacobian functions.
The function \id{jacHeat3} sets up the Jacobian in the special case that MGRID,
the number of node points used in the central difference method, is 3. For MGRID
$\geq$ 4, we use the function \id{jacHeat}.

The main program is written in the same way it was written in
\id{idaHeat2D\_kry} and \id{idaHeat2D\_bnd} but with a few exceptions. In order
to use the {\sunlinsolklu} solver and associated {\sunmatsparse}
matrix type, the user must determine the number of non-zero
(\id{nnz}) variables and there is a conditional statement to check the size of
\id{MGRID} in order to determine which \id{jacHeat} function to use.

The user-supplied function \id{jacHeat3} specifies the values of the Jacobian
matrix for the \id{MGRID}=3 case for each of the three datatypes needed for CSC
format: column pointers (\id{colptrs}), actual data values (\id{data}), and row
value of the data stored (\id{rowvals}). 

The user-supplied function \id{jacHeat} defines the structure of the Jacobian
matrix for a general \id{MGRID} size greater than or equal to 4 in CSC format
and fills in the three datatypes as needed. The system Jacobian matrix is
defined as $J = \partial F/ \partial u + \alpha \partial F/ \partial u'$ with
\id{cj} $=\alpha$ as before. The column-based structure, which was determined
heuristically, was generalized for any size in the allowable range and to allow
for the appropriate number of repeats within the structure of the Jacobian
matrix. The structure's pattern was found by splitting the matrix into
\id{MGRID} blocks and determining the pattern within each block separately for
each of the datatypes.

The {\ida} package also includes support for \id{SUPERLU\_MT}, the
parallel sparse direct solver. The \id{idaHeat2D\_sps} example has
been included to demonstrate \id{SUPERLU\_MT}. It is very similar to
\id{idaHeat2D\_klu}.

Sample output from \id{idaHeat2D\_klu} follows.
%%
\includeOutput{idaHeat2D\_klu}{../../examples/ida/serial/idaHeat2D_klu.out}
%%
%%
%-------------------------------------------------------------------------------
